package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/partition-list/description/
 * <p>
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * <p>
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * @author hanjuntao
 * @date 2025/8/11 0011
 */
public class L_86_分隔链表 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(2);

        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//        node5.next = node6;

        ListNode result = partition(node1, 0);
        ListNode.print(result);
    }

    /**
     * 思路：
     *
     * 1. 创建两个链表，一个链表存放小于x的节点，一个链表存放大于等于x的节点
     * 2. 遍历链表，将小于x的节点放入小于链表，将大于等于x的节点放入大于等于链表
     * 3. 将小于链表和大于等于链表连接起来
     *
     *
     * 该题为奇偶链表的变种, 不过更复杂一点，两个链表都可能存在空指针，所以需要判断
     *
     *
     *
     * @param head
     * @param x
     * @return
     */
    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode bigHead = null;
        ListNode bigCurr = null;

        ListNode prev = null;
        ListNode curr = head;
        ListNode tail = null;
        while (curr != null) {
            ListNode next = curr.next;

            // 判断节点是否大于等于x
            if (curr.val >= x) {
                if (next == null) {
                    tail = prev;
                }

                // 如果当前节点是头节点，则将头节点指向下一个节点
                if (curr == head) {
                    head = next;
                }

                if (bigHead == null) {
                    bigHead = curr;
                    bigCurr = bigHead;
                } else {
                    bigCurr.next = curr;
                    bigCurr = bigCurr.next;
                }

                // 从原链表删除
                if (prev != null) {
                    prev.next = curr.next;
                }
                curr.next = null;
            } else {
                if (next == null) {
                    tail = curr;
                }
                prev = curr;
            }

            curr = next;
        }

        // 链接两个链表, 两个链表都存在空的可能性，所以需要判断
        if (tail != null) {
            tail.next = bigHead;
        } else {
            head = bigHead;
        }
        return head;
    }
}
